package org.example;

public class Test5 {
    //leetcode 206 反转链表 https://leetcode.cn/problems/reverse-linked-list/description/

    /**
     * 方法一：双指针
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = null,cur = head, nextNode = null;
        while (cur != null) {
            nextNode = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextNode;
        }
        return prev;
    }

    /**
     * 方法二：递归
     * @param prev
     * @param cur
     * @return
     */
    public ListNode reverse(ListNode prev,ListNode cur) {
        if (cur == null) return prev;
        ListNode temp = cur.next;
        cur.next = prev;
        return reverse(cur,temp);
    }

    public ListNode reverseList1(ListNode head) {
        return reverse(null,head);
    }
}
